module Loader
  class Loader::DependencySolver

    class CircularDependenceException < Exception; end
    class MissingDependencyException < Magic::ExceptionWrapper; end
    
    def initialize
      @dependencies = {}
    end
    
    def add_dependency subject, dependencency
      @dependencies[subject] ||= []
      @dependencies[subject] << dependencency
    end
    
    def immediate_dependecies subject
      @dependencies[subject] || []
    end
    
    def solve_dependencies subject
      reverse_solution = _solve_dependencies(subject)
      reverse_solution.shift
      reverse_solution.reverse
    end
    
    private
    
    def _solve_dependencies subject
      new_paths = [[subject]]
      solution = []
      while(new_paths.length > 0)
        paths = new_paths.dup
        new_paths = []
        paths.each do |path|
          immediate_dependecies(path.last).each do |dep|
            if path.include? dep
              raise CircularDependenceException.new("Circular dependence in #{path.inspect} with #{dep}")
            end
            branch = (path.dup << dep)
            new_paths << branch
            if solution.length < branch.length
              solution = branch
            end
          end
        end
      end
      solution
    end
    
  end
end